package com.xiaoyu.arrays;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: DS_and_A
 * @description: 求众数升级版  --> 最简单的方法还是使用hashmap存储,然后判断,简单快捷,但是时间和空间都不符合要求..
 *
 * 给定一个大小为n的整数数组，找出其中所有出现超过⌊ n/3 ⌋次的元素。
 *
 * 进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。
 *
 * 输入：[1,1,1,3,3,2,2,2]
 * 输出：[1,2]
 *
 * @author: YuWenYi
 * @create: 2021-05-09 15:51
 **/
public class MajorityElement2 {

    //摩尔投票法:大于3分之一的众数最多出现两个
    public static List<Integer> majorityElement(int[] nums) {
        ArrayList<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        //初始化两个候选人
        int candi1 = nums[0];int count1 = 0;
        int candi2 = nums[0];int count2 = 0;

        //配对阶段:找出两个候选人
        for (int num : nums) {
            if (candi1 == num){
                count1++;
                continue;
            }
            if (candi2 == num){
                count2++;
                continue;
            }
            if (count1 == 0){
                candi1 = num;
                count1++;
                continue;
            }
            if (count2 == 0){
                candi2 = num;
                count2++;
                continue;
            }
            //能到这里,说明num既不等于candi1,也不等于candi2
            count1--;
            count2--;
        }

        //计数阶段
        // 找到了两个候选人之后，需要确定票数是否满足大于 N/3
        count1 = 0;
        count2 = 0;
        for (int num : nums) {
            if (candi1 == num) count1++;
            else if (candi2 == num) count2++;
        }

        if (count1 > nums.length/3) res.add(candi1);
        if (count2 > nums.length/3) res.add(candi2);

        return res;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,1,1,3,3,2,2,2};
        List<Integer> element = majorityElement(nums);
        System.out.println(element);
    }

}
